1. Technical Field
The present invention relates in general to managing communications networks, and in particular, to a method and system for providing increased flexibility in processing data packets. More particularly, the present invention relates to a method and system for computing a frame check sequence (FCS) for a partitioned data packet. Still more particularly, the present invention relates to implementing Cyclic Redundancy Checks (CRCs) utilizing the inherent flexibility of modulo-2 arithmetic with no carries to provide a Cyclic Redundancy Check (CRC) that is adaptable with existing data processing structures and methods.
2. Description of the Related Art
CRC is a well known method for determining the presence of errors in digital transmissions in which discrete units of data, known as packets are delivered. The fundamental principle upon which CRC is based can be expressed equivalently in one of three ways. First, CRC can be described in terms of division of binary numbers. Second, as described by Boudreau et al. in U.S. Pat. No. 3,872,430, CRC may be performed utilizing a division of polynomials. Third, the utility in implementing CRCs is often realized by designing special check circuits in which Exclusive Or (XOR) and other elementary binomial operands generate frame check numbers for use during CRC.
Several types of packet-oriented data transmission systems are currently available. Token Ring, Ethernet, Asynchronous Transfer Mode (ATM), and Synchronous Optical Network (SONET) are examples of such systems which employ error detection and correction techniques such as CRC. When an information packet (sometimes referred to as a xe2x80x9cframexe2x80x9d or xe2x80x9ccellxe2x80x9d) is delivered from a source node to a destination node the receiver will utilize CRC to verify integrity of the transmission. To verify an accurate and successful transmission of an n-bit data packet, M, in accordance with conventional CRC methodologies requires two fundamental steps. First, a divisor P having n+1 bits is selected. For example, and with reference to Spragins p. 279, the divisor utilized in accordance with the IEEE 802 standard is the 33-bit number known as xe2x80x9cCRC-32xe2x80x9d, as follows (the dot xe2x80x9c.xe2x80x9d is for visual convenience only):
10000010.01100000.10001110.11011011.1.
The next step is to append n 0-bits to the end of the data sequence M. This is equivalent to multiplying M (regarding M as a binary number) by 2n. Data sequence M is then divided by P utilizing modulo-2 arithmetic with, no carries and the remainder, R, is the Frame Check Sequence (FCS) of M. This FCS is then appended to the end (right) of M without the added 0-bits to produce the frame to be transmitted T. If T is correctly transmitted and then divided by P, the remainder is the n-bit number having all zero entries.
Various methods for employing CRC and computing a FCS are well known to those skilled in the art and for a further explanation of conventional CRC methods, reference is made herein to Boudreau et al. U.S. Pat. No. 3,872,430 Stallings, pp. 164-171, and Spragins, Hammond, Pawlikowski, p.279. These references provide a more detailed explanation of CRC calculations and are incorporated herein by reference.
Computation of a FCS for a lengthy data string is cumbersome and hardware intensive. It is therefore often desirable to divide the computation of a FCS for a data packet into several subcomputations which are faster and which impose a lesser degree of hardware overhead. Several techniques are known for performing such CRC computations on subdivided portions of the original data packet. U.S. Pat. No. 5,410,546 (Boyer et al.) and U.S. Pat. No. 5,325,372 (Ish-Shalom), describe one such approach in which partial CRC remainders (adjustment codes) are stored in a table. In this manner, the complete CRC check sequence (sometimes referred to as xe2x80x9ccheck sumxe2x80x9d) may be reconstructed utilizing a software implementation that constructs a FCS from the partial CRC remainders. Such methods may result in lower computation time but do not necessarily reduce hardware and software overhead. In addition, these xe2x80x9ctable lookupxe2x80x9d methods do not support multiple interleaved data streams and are therefore insufficient when utilized with asynchronous systems such as Asynchronous Transfer Mode (ATM).
It can therefore be appreciated that a need exists for an improved CRC computation methodology that capitalizes on existing logic structures to calculate and subsequently combine partial CRCs to form a packet CRC. Such a method and system, if implemented would reduce the overhead required for generating check sequences that provides the flexibility inherent in utilizing partial CRCs.
It is therefore an object of the invention to provide an improved method and system for managing data communications.
It is another object of the invention to provide a method and system for providing increased flexibility in processing data packets.
It is still another object of the invention provide a method and system for computing a frame check sequence (FCS) for a partitioned data packet.
It is a further object of the invention to provide a method and system for implementing Cyclic Redundancy Checks (CRCs) utilizing the inherent flexibility of modulo-2 arithmetic to provide a CRC that is adaptable with existing data processing structures and methods.
The above and other objects are achieved as is now described. An improved method and system for generating a frame check sequence are disclosed. In the preferred implementation, a multiple-bit data string, M, is received in which M is of the form:
anbncndnanxe2x88x921cnxe2x88x921dnxe2x88x921 . . . a2b2c2d2a1b1c1d1.
M is thereafter parsed into multiple subframes of the form:
ananxe2x88x921anxe2x88x922 . . . a2a1;
bnbnxe2x88x921bnxe2x88x922 . . . b2b1;
cncnxe2x88x921cNxe2x88x922 . . . c2c1;
and
dndnxe2x88x921dnxe2x88x922 . . . d2d1.
The subframes are padded with zeros resulting in subframes of the form:
an000anxe2x88x921000anxe2x88x922000 . . . a2000a1000;
0bn000bnxe2x88x921000bnxe2x88x92200 . . . 0b2000b100;
xe2x80x8300cn000cnxe2x88x921000cnxe2x88x9220 . . . 00c2000c10;
and
000dn000dnxe2x88x921000dnxe2x88x922 . . . 000d2000d1.
A partial check sum is then generated for each of the multiple subframes. Finally, each of the partial check sums are added together such that a frame check sequence for M is obtained. In this manner, the sum of the partial check sums is guaranteed to be the same as the check sum for the original complete data packet.